920G - List Of Integers - CodeForces Solution

#include <vector>
#include <cstring>
#include <iostream>

const int maxn = 1.8e7;
bool pr[maxn + 100];
std::vector<long long> pint, f;

void fac(int x) {
  f.clear();
  for (auto i : pint) {
    if (x % i != 0)
      continue;
    if (i * i > x)
      break;
    f.push_back(i);
    while (x % i == 0)
      x /= i;
  }
  if (x != 1)
    f.push_back(x);
}

int solve(int val) {
  int ret = 0;
  int lim = 1 << f.size();
  for (int j = 1; j < lim; j++) {
    int tp = 1, ct = 0;
    for (int i = 0; i < (int)f.size(); i++) {
      if ((j >> i) & 1) {
        tp *= f[i];
        ct++;
      }
    }
    ret += (ct % 2 ? 1 : -1) * val / tp;
  }
  return val - ret;
}

int main() {
  std::memset(pr, true, sizeof(pr));
  pr[0] = pr[1] = false;
  for (int i = 2; i * i <= maxn; i++)
    if (pr[i])
      for (int j = i * i; j <= maxn; j += i)
        pr[j] = false;
  for (int i = 2; i <= maxn; i++)
    if (pr[i])
      pint.push_back(i);
  int cas, x, p, k;
  std::cin >> cas;
  while (cas--) {
    std::cin >> x >> p >> k;
    fac(p);
    int a1 = solve(x), L = x + 1, R = maxn, ans = 0;
    while (L <= R) {
      int mid = L + (R - L) / 2;
      int val = solve(mid) - a1;
      if (val >= k)
        R = mid - 1, ans = mid;
      else
        L = mid + 1;
    }
    std::cout << ans << "\n";
  }
  return 0;
}
// GURNfUXbeFUgWADpjlcjThLMPrjzNxYlxnsXimJDsEcsnXlOdFiUvDGOYjALGsPKLFGSsdmhVGgNCFyjeGJoXlzMcZzpEhCtWcQVpvajxWGEkejTwSLZbwDXWXsAqTYM